package com.lenl.arithmetic.search;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Lenl
 * @version v1.0
 * @create 2022-05-02 16:04
 * @description 二分查找 ,数组必须有序
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr={1,8,10,89,89,89,89,1000,1234};
        int res= binarySearch(arr,0,arr.length-1,9);
        System.out.println(res);

        List<Integer> resList=new ArrayList<>();
        binarySearchAll(arr,0,arr.length-1,89,resList);
        System.out.println(resList.toString());

    }

    //二分法查找
    public  static int binarySearch(int[] arr,int left,int right,int findVal){
        if(left>right){
            return -1;
        }
            //中间值下标
            int mid=(left+right)/2;
            int midVal=arr[mid];
            if(findVal>midVal){
                return binarySearch(arr,mid+1,right,findVal);
            }else if(findVal<midVal){
                return binarySearch(arr,left,mid-1,findVal);
            }else{
                //找到
                return mid;
            }
    }

    //二分法全查找
    public  static void binarySearchAll(int[] arr, int left, int right, int findVal, List<Integer> res){
        if(left>right){
            return;
        }
        //中间值下标
        int mid=(left+right)/2;
        int midVal=arr[mid];
        if(findVal>midVal){
            binarySearch(arr,mid+1,right,findVal);
        }else if(findVal<midVal){
            binarySearch(arr,left,mid-1,findVal);
        }else{
            //找到
            res.add(mid);
            int temp=mid-1;
            while(true){
                if(temp<0||arr[temp]<findVal){
                    break;
                }else{
                    res.add(temp);
                    temp--;
                }
            }
            temp=mid+1;
            while(true){
                if(temp>arr.length-1||arr[temp]>findVal){
                    break;
                }else{
                    res.add(temp);
                    temp++;
                }
            }
        }
    }

}
